package org.example.myleet.p886;

import java.util.*;

public class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        if (dislikes.length == 0) {
            return true;
        }
        boolean[] set1 = new boolean[n + 1];
        boolean[] set2 = new boolean[n + 1];
        set1[dislikes[0][0]] = true;
        set2[dislikes[0][1]] = true;
        Queue<int[]> uncertain = new LinkedList<>();
        for (int i = 1; i < dislikes.length; ++i) {
            uncertain.offer(dislikes[i]);
        }
        while (!uncertain.isEmpty()) {
            boolean edit = false;
            int size = uncertain.size();
            for (int i = 0; i < size; ++i) {
                int[] dislike = uncertain.poll();
                if (set1[dislike[0]]) {
                    if (set1[dislike[1]]) {
                        return false;
                    }
                    set2[dislike[1]] = true;
                    edit = true;
                } else if (set2[dislike[0]]) {
                    if (set2[dislike[1]]) {
                        return false;
                    }
                    set1[dislike[1]] = true;
                    edit = true;
                } else {
                    uncertain.add(dislike);
                }
            }
            if (!edit) {
                Arrays.fill(set1, false);
                Arrays.fill(set2, false);
                int[] dislike = uncertain.poll();
                set1[dislike[0]] = true;
                set2[dislike[1]] = true;
            }
        }
        return true;
    }
}
